package com.dkd.day2025513;

public class BubblingSort {
    public static void main(String args[]) {
        int arr[] = {1, 5, 3, 2, 4};
        quickSort(arr);
        System.out.println(arr);
        for(int i:arr){
            System.out.println(i);
            System.out.println("看看我运行了吗");
        }
    }

    //冒泡排序
    public static void bubblingSort(int[] arr) {
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    //插入排序，自己写
    public static void insertSort(int[] arr) {
        //就是将一个元素插入到已经排好序的数组中，使得这个数组依然有序
        for(int i=0;i<arr.length-1;i++){
            //默认是第一个元素是已经排好序的
            int end  = i;
            int temp = arr[end+1];
            while(end>=0){
                //数值比较打时候，交换位置
                if(arr[end]>temp){
                    arr[end+1] = arr[end];
                    end--;
                }else {
                    //相等或小于的时候，确认位置，结束循环
                    arr[end+1]  = temp;
                    break;
                }
            }

        }
    }

    //希尔排序
    //
    public static void shellSort(int[] arr) {
        //希尔排序，就是将一个数组按照一定步长进行分组，然后对每一组进行插入排序，再按照一定步长进行分组，对每一组进行插入排序，直到步长为1，再对整个数组进行插入排序
        int gap = arr.length/2;
        while(gap>0){
            //步长为gap,每次都按照步长进行分组
            for(int i=0;i<arr.length-gap;i++){
                int end = i;
                System.out.println("i="+i);
                int temp = arr[end+gap];
                while(end>=0){
                    if(arr[end]>temp){
                        arr[end+gap] = arr[end];
                        //这里应该减去gap
                        end=end-gap;
                    }
                    else {
                        arr[end+gap] = temp;
                        break;
                    }
                }
            }
            gap/=2;
        }
    }

    public static void bubblingSort2(int [] arr){
        for(int i =0; i<arr.length-1;i++){
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] =arr [j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    //选择排序
    //选择排序
    public static void selectSort(int [] arr){
        for(int i=0;i<arr.length-1;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    //快速排序
    public static void quickSort(int [] arr){
        int begin = 0;
        int end = arr.length-1;
        quickSort(arr,begin,end);
    }

    //快速排序
    public static void quickSort(int [] arr,int begin,int end){
        if(begin >= end){
            return;
        }
        int right = begin;
        int left = end;
        int key = arr[begin];
        while(begin<end){
            while(begin<end && arr[begin]<key){
                begin++;
            }
            while(begin<end && arr[end]>key){
                end--;
            }
            int temp = arr[begin];
            arr[begin] = arr[end];
            arr[end] = temp;
        }
        arr[begin] = key;
        quickSort(arr,right,begin-1);
        quickSort(arr,begin+1,left);
    }

}
